COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	queens.2[e82,jmc]	Notes on the  n  queens problem
C00006 ENDMK
C⊗;
queens.2[e82,jmc]	Notes on the  n  queens problem

1. Having done 8 queens by hand, one would like to make a program
that uses all the tricks discovered in this experience.  The
problem is that some of the tricks discover other tricks and
require noticing things.

2. If one starts the search with a queen in the corner, queens in
other corners are excluded both by symmetry and simply because the
queen in one corner covers the other corners.  If one continues
the corner queen start, then the only symmetry left is reflection
in the diagonal.  After another piece has been placed, the images
of that position and its predecessors are excluded by symmetry, but
from that point on, symmetry plays no further role, i.e. at that
point some excluded squares can be marked, and no further symmetry
reasoning is required.

3. In so far as reasoning about symmetry merely excludes a set of
squares, this is much simpler than using the variable  exc included
in the program.  Perhaps the program can purge  exc  of positions
that can't arise in continuations of the position.  Once  exc  has
been eliminated, we can continue with a version of the program that
no longer passes that variable.

	See notebook, but there is very little excuse for exc.

4. Can the notion of the shortest proof that we have all solutions
be used?

5. Finding the smallest non-completable configurations may suggest
mathematical methods.

6. Are the 12 classes of solutions of 8 queens all different on torus?

7. The 12 solutions are

1. 15863724 ≡ 6 ≡ 8
2. 16837425
3. 24683175 ≡ 4 ≡ 8 ≡ 6
4. 25713864 ≡ b
5. 25741863 rigid
6. 26174835 ≡ 3 ≡ b ≡ 1
7. 26831475
8. 27368514 ≡ 1 ≡ 3
9. 27581463 rigid
a. 35281746
b. 35841726 ≡ 7 ≡ 4 ≡ 6
c. 36258174 rigid

8. Check on occupancy of diagonals in the solutions.

9. Check the existence of colinearity in solutions.  There was some
reference that speculated about the existence of solutions with no
three queens in a line.

10. Triangles can show the non-completablility of a 4 by 4 solution
in the corner of at least 11 by 11, 12 by 12 and 14 by 14.  There
may be a more general result if we can limit the number of queens
in a right triangle.  In particular, a triangle with 4 on a side
admits only 2 queens and a triangle 7 on a side admits only 4.